package com.fh.binarysearch;

/**
 * T33. 搜索旋转排序数组
 * @author: fuhao
 * @date: 2025/10/14 21:44
 */
public class T33Search {
    class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length;
            // 处理空数组的边界情况
            if (n == 0) {
                return -1;
            }
            // 如果数组只有一个元素，直接判断
            if (n == 1) {
                return nums[0] == target ? 0 : -1;
            }

            int left = 0;
            int right = n - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2; // 防止溢出
                // 如果找到目标，直接返回索引
                if (nums[mid] == target) {
                    return mid;
                }

                // 判断左半部分 [left, mid] 是否有序
                if (nums[left] <= nums[mid]) {
                    // 如果目标值在有序的左半部分范围内
                    if (nums[left] <= target && target < nums[mid]) {
                        right = mid - 1; // 在左半部分继续搜索
                    } else {
                        left = mid + 1;  // 否则去右半部分搜索
                    }
                }
                // 否则，右半部分 [mid, right] 是有序的
                else {
                    // 如果目标值在有序的右半部分范围内
                    if (nums[mid] < target && target <= nums[right]) {
                        left = mid + 1;  // 在右半部分继续搜索
                    } else {
                        right = mid - 1; // 否则去左半部分搜索
                    }
                }
            }

            // 未找到目标值
            return -1;
        }
    }
}
